Before the widespread use of caching in the Internet, an item of content (a content object) requested by a client was likely provided by the original content server (the source of the content object). The content source and the client were typically located at a substantial distance from each other, which often led to slow response times, low bandwidths, high loss rates, and lack of scalability. Response times, bandwidths, and loss rates could also be significantly affected when multiple clients attempted to request an object from the content source at the same time.
Different forms of caching, such as content delivery networks, have helped to overcome some of these problems. Generally, content delivery networks place servers, which may be more specifically referred to as caching proxies, nearer to clients. Content objects can be replicated and cached at each of the caching proxies. Caching of content on caching proxies closer to clients has resulted in a number of improvements, including reduced response times, higher bandwidths, lower loss rates, improved scalability, and reduced requirements for network (backbone) resources.
Content delivery networks work well when the size of the content is relatively small in comparison to the size of the caches. For example, a Web page is generally much less than a megabyte in size. As such, this kind of content can be practically replicated at each caching proxy. Multiple instances of Web content can be stored on each caching proxy without the need for substantial memory resources, or without consuming a significant segment of available memory.
However, caching can be problematic due to the proliferation of multimedia content. Due to the large size of typical multimedia objects, a full-object caching strategy will quickly exhaust the cache space. That is, even a large cache can hold only a few items of multimedia content before getting filled. For example, a video of DVD (digital video disk) quality may be up to 4.7 gigabytes (GB) in size and up to two hours long (based on Moving Picture Expert Group-2 compression). Consequently, a 50 GB cache can hold only about ten DVD-quality videos. Thus, once the cache is filled, it is necessary to begin removing non-active objects from the cache in order to make room for an incoming object.
Presently, prefix caching and segment-based caching are the two techniques typically used to resolve the issue of a full proxy cache. In general, prefix caching works well when most clients access the initial segments of media objects. It also reduces startup latency by immediately serving the cached prefix from the proxy to the client while retrieving subsequent segments from the origin server. However, in prefix caching, the static determination of the prefix size plays a vital role in the system's performance.
In general, segment-based caching methods have been developed for increased flexibility. These methods also cache segments of media objects rather than entire media objects. Typically two types of segmentation strategies are used. The first type uses uniformly sized segments. For example, caching uniformly sized segments of layer-encoded video objects. The second type uses exponentially sized segments. In this strategy, media objects are segmented with increasing lengths; for example, the segment length may double. This strategy is based on the assumption that later segments of media objects are less likely to be accessed. In some cases, a combination of these methods may be utilized. That is, in which constant lengths and exponentially increased lengths are both considered. This type of method also favors the beginning segments of media objects.
However, the prefix and segmentation-based caching methods discussed herein do not address the following considerations. First, a users accesses to media objects typically represent a skewed pattern: most accesses are for a few popular objects, and these objects are likely to be watched in their entirety or near entirety. This is often true for movie content in a virtual office meetings and training videos in a corporation environment. That is, a heuristic segment-based caching strategy with a predefined segment size, exponential or uniform, which always favorably caches the beginning segments of media objects does not account for the fact that most accesses are targeted to a few popular objects.
Second, the access characteristics of media objects are dynamically changing. That is, the media object's popularity and most watched segments may vary with time. For example, some objects may be popular for an initial time period where most users access entire objects. Then, as the time goes on, there may be fewer requests for these objects and there may be fewer user accesses to the later segments of the objects. In this scenario, using a fixed strategy of caching several early segments may not work, since during the initial time period this may overload the network as later segments need to be retrieved frequently; then during the later time, caching all the initial segments may become wasteful of resources. This lack of adaptiveness in the existing proxy caching schemes may render proxy caching to be ineffective.
Accordingly, a more efficient way of caching content objects for end-users is desirable. Embodiments of the present invention provide such an improvement.